import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution934 {

    int[] dx=new int[]{1,0,-1,0};
    int[] dy=new int[]{0,1,0,-1};

    public int shortestBridge(int[][] grid) {
        int[][] color=new int[grid.length][grid[0].length];
        int cur=0;
        for (int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                if (grid[i][j]==1 && color[i][j]==0){
                    cur++;
                    dfs(grid,i,j,color,cur);
                }
            }
        }
        Set<List<Integer>> set1=new HashSet<>();
        for (int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                if (color[i][j]==1){
                    for (int k=0;k<4;k++){
                        int x=i+dx[k];
                        int y=j+dy[k];
                        if (x>=0 && x<grid.length && y>=0 && y<grid[0].length && grid[x][y]==0){
                            set1.add(Arrays.asList(i,j));
                        }
                    }
                }
            }
        }
        Set<List<Integer>> set2=new HashSet<>();
        for (int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                if (color[i][j]==2){
                    for (int k=0;k<4;k++){
                        int x=i+dx[k];
                        int y=j+dy[k];
                        if (x>=0 && x<grid.length && y>=0 && y<grid[0].length && grid[x][y]==0){
                            set2.add(Arrays.asList(i,j));
                        }
                    }
                }
            }
        }
        int ans=Integer.MAX_VALUE;
        for (List<Integer> l1 : set1) {
            for (List<Integer> l2 : set2) {
                ans=Math.min(ans,Math.abs(l1.get(0)-l2.get(0))+Math.abs(l1.get(1)-l2.get(1)));
            }
        }
        return ans-1;
    }

    private void dfs(int[][] grid, int x, int y, int[][] color, int cur) {
        color[x][y]=cur;
        for (int i=0;i<4;i++){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if (xx>=0 && xx<grid.length && yy>=0 && yy<grid[0].length && grid[xx][yy]==1 && color[xx][yy]==0){
                dfs(grid,xx,yy,color,cur);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution934().shortestBridge(new int[][]{{1,1,1,1,1},{1,0,0,0,1},{1,0,1,0,1},{1,0,0,0,1},{1,1,1,1,1}}));
    }
}
